//剑指offer24 二叉树中和为某一路径的值
//https://blog.nowcoder.net/n/b9372be69aa043dfa0e96de52014a8bd?f=comment
import java.util.ArrayList;
import java.util.Stack;

/*
class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val){
	this.val=val;
	}
}
*/

public class Solution{
	private ArrayList<ArrayList<Integer>> result=new ArrayList<>();
	private Stack<Integer> temp=new Stack<>();
	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target){
		if(root==null) return result;
		find(root,target,0);
		return result;
	}
	
	private void find(TreeNode root,int target,int cur){
		if(cur==target&&root==null){
			result.add(new ArrayList(temp));
			return;
		}
		if(root==null){//这一步不能和上面的cur==target&&root==null互换
			return;
		}
		temp.push(root.val);
		find(root.left,target,cur+root.val);
		temp.pop();
		
		if(root.left==null&&root.right==null){
			return;
		}
		
		temp.push(root.val);
		find(root.right,target,cur+root.val);
		temp.pop();
	}
}